package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 20:54 2020/3/24
 * @Description  leetcode3
 */

import java.util.HashMap;
import java.util.HashSet;

public class LeetCode_03 {



    // 双指针:p1主要是向前搜索，p2主要是用于长度计算

    public int lengthOfLongestSubstring(String s) {

        HashSet<Character> set = new HashSet();
        int p1 = 0;
        int p2 = 0;
        int ans = 0;

        // 小心空串
        while(p1<s.length() || p2<s.length()){
            // 只有前面那个和p1所指向的相同字符字符被移除，也就是说必须从上一个此字符下一个开始计数
            // p1<s.length()是为了预防空串导致   ans = Math.max(ans,p1-p2);执行不到
            if( p1<s.length()&& !set.contains(s.charAt(p1))){
                set.add(s.charAt(p1));
                p1++;
            }else{
                ans = Math.max(ans,p1-p2);
                set.remove(s.charAt(p2));
                p2++;
            }

        }
        return ans;
    }



    // 使用HashMap优化过的
    class Solution {

        public int lengthOfLongestSubstring(String s) {
            HashMap<Character,Integer> map = new HashMap();
            int ans = 0;
            for(int i = 0,j=0;i<s.length();i++){
                if(map.containsKey(s.charAt(i))){
                    // 在此部分有可能产生指针回溯（导致j向左移动）如abba
                    j = Math.max(j,map.get(s.charAt(i)));

                }
                ans = Math.max(ans,i-j+1);
                map.put(s.charAt(i),i+1);
            }
            return ans;
        }

    }

}
